# Permutation
# array [1, 2, 3]
# permuation
# [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
#
# curr_perm []
# array [1, 2, 3]
# 1
# new_array [2, 3]
# curr_perm [1]

# def permutation(array):
# Parameters:
# - array: 求排列的数组
# - curr_perm: 当前求到的排列
# - perms: 保存所有排列的数组
def perm_helper(array, curr_perm, perms):
  # Q: len(array) == 0 意味着什么？
  # A: array 中已经没有数字要求排列了
  if len(array) == 0 and len(curr_perm) != 0:
    perms.append(curr_perm)
  else:
    for i in range(len(array)):
      # 求除了位置 i 之外的其它所有元素
      new_array = array[:i] + array[i + 1:]
      # 用当前 i 位置的元素构成一个排列
      new_perm = curr_perm + [array[i]]
      # 递归这个过程
      perm_helper(new_array, new_perm, perms)

def permutation(array):
  perms = []
  perm_helper(array, [], perms)
  return perms

print(permutation([1, 2, 3]))
